Seam Carving in Julia

x
 
md"# Seam Carving in Julia"

4.4 μs

Functions

5.9 μs

xxxxxxxxxx
 
using Images, ImageView, ImageFiltering, Statistics, ImageMagick, PlutoUI

17.6 s

brightness (generic function with 1 method)

x
 
# Convert RGB to brigthness
function brightness(img_element::AbstractRGB)
    return mean((img_element.r + img_element.g + img_element.b))
end

22.2 μs

find_energy (generic function with 1 method)

xxxxxxxxxx
 
# Find energy, how important a pixel is to the image to us.
function find_energy(img)
    energy_x = imfilter(brightness.(img), Kernel.sobel()[2])
    energy_y = imfilter(brightness.(img), Kernel.sobel()[1])
    
    return sqrt.(energy_x.^2 + energy_y.^2)
end

31 μs

normalize_greyness (generic function with 1 method)

xxxxxxxxxx
 
# To help view energy image, normalize values to 0-1
function normalize_greyness(array)
    max, _ = findmax(array)
    array = array./max
    return array
end

26.5 μs

grey_to_rgb (generic function with 1 method)

x
 
# Convert a value to RGB to view arrays as images
function grey_to_rgb(brigthness)::RGB
    return RGB(brigthness, brigthness, brigthness)
end

30.4 μs

find_seam_at (generic function with 1 method)

xxxxxxxxxx
 
# Finds the seam of least energy starting at given position
function find_seam_at(next_elements, element)
    seam = zeros(Int, size(next_elements)[1])
    seam[1] = element
    
    for i = 2 :length(seam)
        seam[i] = seam[i-1] + next_elements[i, seam[i-1]]
    end
    
    return seam
end

28.2 μs

find_seam (generic function with 1 method)

x
 
# Finds the best starting point and the seam from there
function find_seam(energy)
    energy_map, next_elements = find_energy_map(energy)
    
    _, min_element = findmin(energy_map[1, :])
    
    return find_seam_at(next_elements, min_element)
end

37.4 μs

find_energy_map (generic function with 1 method)

x
 
# Calculate the combined energy needed for each pixel from bottom to top
function find_energy_map(energy)
    energy_map = zeros(size(energy))
    energy_map[ end, : ] = energy[ end, : ]
    
    next_elements = zeros(Int, size(energy))
    
    for i = size(energy)[1]-1 :-1:1
        for j = 1 :size(energy)[2]
            left = max(1, j-1)
            right = min(j+1, size(energy)[2])
            
            local_energy, next_element = findmin(energy_map[i+1, left:right])
            energy_map[i,j] = local_energy + energy[i,j]
            
            next_elements[i,j] = next_element - 2
            
            if left == 1
                next_elements[i,j] += 1
            end
        end
    end
    
    return energy_map, next_elements
end

41.8 μs

draw_seam (generic function with 1 method)

x
 
function draw_seam(image, seam)
    image_with_seam = copy(image)
    for i = 1 : size(image_with_seam)[1]
        image_with_seam[i, seam[i]] = RGB(1, 0, 0)
    end
    
    return image_with_seam
end

32.9 μs

remove_seam (generic function with 1 method)

46.7 μs

seam_carving (generic function with 1 method)

x
 
function seam_carving(img, res)
    if res < 0 || res > size(img)[2]
        error("resolution not acceptable")
    end
    
    for i = (1:size(img)[2] - res)
        energy = find_energy(img)
        seam = find_seam(energy)
        img = remove_seam(img, seam)
    end
    return img
end

43.2 μs

get_all_carved (generic function with 1 method)

xxxxxxxxxx
 
# Make all carved variants of the original image
function get_all_carved(img, amount)
    
    if(amount < 0 || amount > size(img)[2])
        error("amount not acceptable")
    end
    
    all_images = []
    
    for i = (1:amount)
        energy = find_energy(img)
        seam = find_seam(energy)
        img = remove_seam(img, seam)
        push!(all_images,  img)
    end
    return all_images
end

30.6 μs

Examples

3.8 μs

The original image

8.8 μs

x
 
begin
    test_image = imresize(load("fox.jpg"), ratio=1/4.5)
    test_image = RGB{Float32}.(test_image)
end

222 ms

x
 
size(test_image)

3.7 μs

energy

459×675 Array{Float64,2}:
 0.08230626182890809   0.03924633733582069   …  0.12013708121153048
 0.08204016971261124   0.03615509192693736      0.1452321975682269
 0.06117055721409237   0.07197040239680258      0.08148767262441961
 0.1579527126513256    0.13794121945113755      0.05316306337434861
 0.14057949647072956   0.07945411130085152      0.03812833195152889
 0.21019070310238272   0.12611102359351106   …  0.16439778998489007
 0.15806071985941766   0.05101811349756884      0.09896866880767466
 ⋮                                           ⋱  
 0.030956177996254306  0.03615507091560697      0.062391724730204975
 0.06907769979945161   0.03448138488543452      0.0576724554581597
 0.023529440164585358  0.02977717948065177   …  0.04000427991459951
 0.04742507232365957   0.05030185791220897      0.057107305327577386
 0.02630661388029809   0.03553835112719368      0.027116291064753127
 0.024956750583578716  0.037203320918664774     0.04185369598012464

x
 
energy = find_energy(test_image)

10.4 ms

This image below shows the "energy" or how important each pixel is

5.1 μs

energy_image

xxxxxxxxxx
 
energy_image = grey_to_rgb.(energy)

1.8 ms

459×675 Array{Float64,2}:
 13.4415     13.3322     13.4144     13.4028     …  5.53075     5.49632    5.52851
 13.4258     13.3592     13.293      13.3202        5.44132     5.40837    5.46554
 13.3532     13.3438     13.323      13.2763        5.42115     5.32031    5.36379
 13.3927     13.292      13.2718     13.2658        5.30259     5.32483    5.28231
 13.4433     13.2347     13.1541     13.1492        5.29658     5.22914    5.23736
 13.4577     13.3027     13.1553     13.1291     …  5.16706     5.19923    5.22769
 13.3546     13.2475     13.1766     13.0791        5.03396     5.06329    5.20093
  ⋮                                              ⋱                         
  0.14147     0.136973    0.145926    0.113835      0.13022     0.143386   0.195931
  0.15812     0.110514    0.100818    0.103997      0.0959613   0.133539   0.176819
  0.109384    0.0890423   0.0760325   0.0661278  …  0.0894212   0.119147   0.137979
  0.0961168   0.0858545   0.0592651   0.0642783     0.0850369   0.0979748  0.0989295
  0.0512634   0.0486917   0.0355526   0.0694598     0.0518985   0.0478337  0.0418222
  0.0249568   0.0372033   0.0131534   0.0587131     0.00623912  0.0147059  0.0418537

459×675 Array{Int64,2}:
 1  2  0  -1   0  -1   1   0   1   1   1  …   0  -1   0  -1   1   0  -1   1   0  -1
 1  2  1   0   1   0   1   0  -1   1   1     -1   1   1   1   0   1   0  -1   0  -1
 1  2  1   1   1   0  -1  -1  -1   1   1     -1  -1   1   1   0  -1   1   0   1   0
 1  2  1   0   1   1   0  -1  -1  -1   1     -1   1   0  -1  -1   0  -1   1   0  -1
 1  2  1   0  -1   1   1   0  -1  -1   1     -1   0  -1  -1   1   1   0  -1  -1  -1
 1  2  1   0   1   1   1   1   1   0  -1  …   1   0  -1  -1   1   1   1   0  -1  -1
 1  1  1   1   0   1   1   0  -1   1   1      0  -1  -1   0   1   1   0  -1  -1  -1
 ⋮                 ⋮                   ⋮  ⋱   ⋮                   ⋮              
 1  2  0   1   0  -1   1   0   1   1   0      0  -1  -1  -1   0  -1   0  -1  -1  -1
 1  2  1   0  -1   1   0  -1   1   0  -1     -1  -1  -1  -1  -1   0  -1   0  -1  -1
 1  2  0  -1   1   0  -1  -1   1   0  -1  …   0  -1  -1  -1  -1   0  -1   0  -1  -1
 1  2  0  -1   1   1   0  -1   1   1   0     -1  -1  -1  -1  -1   1   0   1   1   0
 0  2  0  -1  -1   1   0  -1  -1   1   0     -1   0  -1   0  -1   1   1   0  -1  -1
 0  0  0   0   0   0   0   0   0   0   0      0   0   0   0   0   0   0   0   0   0

xxxxxxxxxx
 
energy_map, next_elements = find_energy_map(energy)

34.5 ms

This image below shows the the combined energy needed for a pixel at that position.

5.9 μs

xxxxxxxxxx
 
begin
    normalized = normalize_greyness(energy_map)
    energy_map_img = grey_to_rgb.(normalized)
end

3 ms

best_seam

Int641

450

451

452

453

454

455

456

457

458

459

xxxxxxxxxx
 
best_seam = find_seam(energy)

33.7 ms

Here the first best seam marked in red

8.2 μs

image_with_best_seam

xxxxxxxxxx
 
image_with_best_seam = draw_seam(test_image, best_seam)

792 μs

Any1

463

464

465

466

467

468

469

470

471

472

x
 
begin
    max_reduction = size(test_image)[2] * 0.7
    all_carved_images = get_all_carved(test_image, max_reduction)
end

33 s

151

55.4 μs

With all the carved variants we can preview each one in series

8 μs

2.4 μs

xxxxxxxxxx
 
test_image

600 ns